package com.atguigu.algorithm;

import java.util.Arrays;

class Suff implements Comparable<Suff>{
    public String str;
    public int index;
    public Suff(int index,String str){
        this.str=str;
        this.index=index;
    }
    @Override
    public int compareTo(Suff o2){
        return str.compareTo(o2.str);
    }
}
public class StringMatch {
    public static void main(String[] args) {
        String string1="ABABABABB";
        String string2="BABB";
        StringMatch stringMatch=new StringMatch();
        Suff[] s=stringMatch.SuffixArray(string1);
        for(int i=0;i<s.length;i++){
            System.out.println(s[i].str+" "+s[i].index);
        }
        Arrays.sort(s);
        System.out.println();
        for(int i=0;i<s.length;i++){
            System.out.println(s[i].str+" "+s[i].index);
        }
    }
    public Suff[] SuffixArray(String string){
        int len=string.length();
        Suff[] sa=new Suff[len];
        int j=0;
        for(int i=len;i>0;i--){
            sa[j]=new Suff(i-1,string.substring(len-i,len));
            j++;
        }
        return sa;
    }
    public Suff[] getSA(String src){
        int strLength=src.length();
        int[] rk=new int[strLength];
        Suff[] suffixArray=new Suff[strLength];
        for(int k=1;k<=strLength;k*=2){
            for(int i=0;i<strLength;i++){
                String suff=src.substring(i,i+k>strLength?strLength:i+k); //注意越界
                suffixArray[i]=new Suff(i,suff);
            }
            if(k==1) //一个字符
                {
                    Arrays.sort(suffixArray);
                }else{
                //填充完成，开始排序
                final int kk=k;
                Arrays.sort(suffixArray,(o1,o2)->{
                    //不是基于字符串比较，而是利用之前的rank
                    int i=o1.index;
                    int j=o2.index;
                    if(rk[i]==rk[j]){ //如果o1和o2的前半段相同
                        try{
                            return rk[i+kk/2]-rk[j+kk/2];
                        }catch (ArrayIndexOutOfBoundsException e){
                            return o1.str.length()-o2.str.length();
                        }
                    }else{
                        return rk[i]-rk[j];
                    }
                } );
            }
        }
        //排序后，完成生产rank，即给定下标，给出排名
        int r=0;
        rk[suffixArray[0].index]=r;
        for(int i=1;i<strLength;i++){
            if(suffixArray[i].compareTo(suffixArray[i-1])==0){ //内容相同
                rk[suffixArray[i].index]=r; //索引-排名  给定索引，知道排名
            }else{
                rk[suffixArray[i].index]=++r;
            }
        }
        return suffixArray;
    }
}
